Efficiently Calculating Legendre Symbols

The following note describes an algorithm for computing Legendre symbols in a relatively efficient way. Note that because this requires integer factorisation, the method is not fast for very large numbers. Also note that these assume that we are working modulo a prime.

Illustrative Example

We first verify that \(7919\) is prime. Now, we apply multiplicity by fully factorising \(4950\):

Now we can take out any even powers of any term, since these are trivially quadratic residues, in this case we just have \(3^2\) to remove:

Now, we can explicitly evaluate the Legendre symbol of \(2\) using this result, and since \(7919 \equiv -1 \pmod 8\), \(2\) is a quadratic residue:

For all the odd primes, we apply the law of quadratic reciprocity to flip these symbols. Note that \(7919 \equiv 3 \pmod 4\), and hence whether or not we need to negate the symbols depends only on the "numerator". In this case \(3\) is the only one which is \(3\) modulo \(4\), so we introduce one negative:

Then we reduce all the numerators modulo the denominators, which is valid since we are working in the same residue class.

and we are effectively back where we started, in the sense that each of these symbols can be evaluated using the method described here from top to bottom. That is, we explicitly evaluate the symbol of \(2\), we factorise any numerators, and we flip any symbols with prime numerators, until everything is reduced to something which is an obvious square, or \(2\) which we know how to evaluate explicitly.

It is however worth mentioning that at any point, if it is desired to work with negative numerators within the same residue class, we can pull out a \(-1\) using multiplicity, and then evaluate this explicitly using this result.

Generalised Results

This is an attempt to generalise the above, however the example above is chosen to include all of the possible useful results below, and hence is a better illustration of the process.